package BinaryTree;

import com.sun.source.tree.Tree;

import java.nio.file.StandardOpenOption;
import java.util.*;

public class BinaryTree implements Operations {

    public int nodeCount;//结点个数

    public int leafNodeCount;//叶子结点个数

    //创建树
    @Override
    public TreeNode createTree() {
//        TreeNode A = new TreeNode('A');
//        TreeNode B = new TreeNode('B');
//        TreeNode C = new TreeNode('C');
//        TreeNode D = new TreeNode('D');
//        TreeNode E = new TreeNode('E');
//        TreeNode F = new TreeNode('F');
//        TreeNode G = new TreeNode('G');
//        TreeNode H = new TreeNode('H');
//
//        A.leftNode = B;
//        A.rightNode = C;
//        B.leftNode = D;
//        B.rightNode = E;
//        E.rightNode = H;
//        C.leftNode = F;
//        C.rightNode = G;

        TreeNode A = new TreeNode('3');
        TreeNode B = new TreeNode('1');
        TreeNode C = new TreeNode('7');
        TreeNode D = new TreeNode('6');
        TreeNode E = new TreeNode('8');

        A.leftNode = B;
        A.rightNode = C;
        C.leftNode = D;
        C.rightNode = E;


        return A;
    }

    public int i;
    public TreeNode creatTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.leftNode = creatTree(str);
            root.rightNode = creatTree(str);
        } else {
            i++;
        }
        return root;
    }

    //前序遍历
    @Override
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.print(root.val + " ");

        preOrder(root.leftNode);
        preOrder(root.rightNode);
    }

    //非递归前序遍历
    public void preorderTraversal(TreeNode root) {
        TreeNode curNode = root;
        Stack<TreeNode> stack = new Stack<>();

        while (curNode != null || !stack.isEmpty()) {
            while (curNode != null) {
                System.out.print(curNode.val + " ");
                stack.push(curNode);
                curNode = curNode.leftNode;
            }
            TreeNode topNode = stack.pop();
            curNode = topNode.rightNode;
        }

    }

    //中序遍历
    @Override
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        inOrder(root.leftNode);
        System.out.print(root.val + " ");
        inOrder(root.rightNode);
    }

    //非递归中序遍历
    public void inorderTraversal(TreeNode root) {
        TreeNode curNode = root;
        Stack<TreeNode> stack = new Stack<>();

        while (curNode != null || !stack.isEmpty()) {
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.leftNode;
            }
            TreeNode topNode = stack.pop();
            System.out.print(topNode.val + " ");
            curNode = topNode.rightNode;
        }

    }
    //后序遍历
    @Override
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        postOrder(root.leftNode);
        postOrder(root.rightNode);
        System.out.print(root.val + " ");
    }

    //非递归后序遍历
    public void postorderTraversal(TreeNode root) {
        TreeNode curNode = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = null;
        while (curNode != null || !stack.isEmpty()) {
            //Boolean flag = false;
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.leftNode;
            }
            if (!stack.isEmpty()) {
                TreeNode topNode = stack.peek();
                if (topNode.rightNode == null || topNode.rightNode == node) {
                    stack.pop();
                    System.out.println(topNode.val);
                    node = topNode;
                } else {
                    curNode = topNode.rightNode;
                }
            }

        }
    }
    //结点个数
    @Override
    public void size(TreeNode root) {
        if (root == null) {
            return;
        }

        if (root != null) {
            nodeCount++;
        }
        size(root.leftNode);
        size(root.rightNode);

    }

    //结点个数
    @Override
    public int size2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return size2(root.leftNode) + size2(root.rightNode) + 1;
    }

    //叶子结点个数
    @Override
    public void getLeafNodeCount1(TreeNode root) {
        if (root == null) {
            return;
        }

        if (root.leftNode == null && root.rightNode == null) {
            leafNodeCount++;
        }

        getLeafNodeCount1(root.leftNode);
        getLeafNodeCount1(root.rightNode);
    }

    @Override
    public int getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.leftNode == null && root.rightNode == null) {
            return 1;
        }

        return getLeafNodeCount2(root.leftNode) + getLeafNodeCount2(root.rightNode);
    }

    //第K层结点个数，从0开始，第一行为第0层
    @Override
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }

        if (root != null && k == 0) {
            return 1;
        }

        return getKLevelNodeCount(root.leftNode, k - 1) +
                getKLevelNodeCount(root.rightNode, k - 1);
    }

    //高度
    @Override
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return Math.max(getHeight(root.leftNode), getHeight(root.rightNode)) + 1;
    }

    //判断val是否存在
    @Override
    public TreeNode find(TreeNode root, char val) {
        if (root == null) {
            return null;
        }

        if (root.val == val) {
            return root;
        }

        TreeNode leftNode = find(root.leftNode, val);
        if (leftNode != null) {
            return leftNode;
        }

        TreeNode rightNode = find(root.rightNode, val);
        if (rightNode != null) {
            return rightNode;
        }

        return null;
    }

    //层序遍历
    @Override
    public void levelOrder(TreeNode root) {
        TreeNode topNode = root;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(topNode);

        while (!queue.isEmpty()) {
            topNode = queue.poll();
            if (topNode.leftNode!= null) {
                queue.offer(topNode.leftNode);
            }
            if (topNode.rightNode != null) {
                queue.offer(topNode.rightNode);
            }
            if (topNode != null) {
                System.out.print(topNode.val + " ");
            }
        }
    }

    public List<List<Character>> levelOrder2(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode topNode = root;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(topNode);

        List<List<Character>> retList = new ArrayList<>();

        while (!queue.isEmpty()) {
            List<Character> list = new ArrayList<>();
            int size = queue.size();
            while (size != 0) {
                topNode = queue.poll();
                size--;
                if (topNode.leftNode != null) {
                    queue.offer(topNode.leftNode);
                }
                if (topNode.rightNode != null) {
                    queue.offer(topNode.rightNode);
                }
                list.add(topNode.val);
            }
            retList.add(list);
        }

        return retList;
    }

    @Override
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        if (root == null) {
            return true;
        }


//        while (root != null) {
//            TreeNode curNode = queue.poll();
//            if (curNode == null) {
//                for (int i = 0; i < queue.size(); i++) {
//                    TreeNode node = queue.poll();
//                    if (node != null) {
//                        return false;
//                    }
//                }
//            } else {
//                queue.add(curNode.leftNode);
//                queue.add(curNode.rightNode);
//            }
//        }

        while (queue.peek() != null) {
            TreeNode curNode = queue.poll();
            queue.add(curNode.leftNode);
            queue.add(curNode.rightNode);
        }

//        while (!queue.isEmpty()) {
//            TreeNode curNode = queue.poll();
//            if (curNode != null) {
//                queue.offer(curNode.leftNode);
//                queue.offer(curNode.rightNode);
//            } else {
//                break;
//            }
//        }

//        //若使用这种循环，会导致每次循环过后queue的size减1，导致无法全部遍历完queue
//        for (int i = 0; i < queue.size(); i++) {
//            TreeNode node = queue.poll();
//            if (node != null) {
//                return false;
//            }
//        }

//        System.out.println(queue.size());

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                return false;
            }
        }

        return true;
    }

    //给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
    //如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }

        if (p == null && q != null || p != null && q == null) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }

        return isSameTree(p.leftNode, q.leftNode) && isSameTree(p.rightNode, q.rightNode);
    }

    //给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
    //如果存在，返回 true ；否则，返回 false 。
    //二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // if (subRoot == null) {
        //     return true;
        // }

        if (root == null && subRoot == null || root != null && subRoot == null) {
            return true;
        }

        if (root == null && subRoot != null) {
            return false;
        }

        if (isSameTree(root, subRoot)) {
            return true;
        }

        //return isSameTree(root.left, subRoot) || isSameTree(root.right, subRoot) || isSameTree(root, subRoot);


        return isSubtree(root.leftNode, subRoot) || isSubtree(root.rightNode, subRoot);
    }

    //给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }

        TreeNode tempNode = root.leftNode;
        root.leftNode = root.rightNode;
        root.rightNode = tempNode;

        invertTree(root.leftNode);
        invertTree(root.rightNode);

        return root;
    }

    //给定一个二叉树，判断它是否是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        int leftH = getHeight(root.leftNode);
        int rightH = getHeight(root.rightNode);

        // if (Math.abs(leftH - rightH) >= 2) {
        //     return false;
        // }

        // isBalanced(root.left);
        // isBalanced(root.right);

        // return false;

        return Math.abs(leftH - rightH) <= 1 && isBalanced(root.leftNode) && isBalanced(root.rightNode);
    }

    //给你一个二叉树的根节点 root ， 检查它是否轴对称。
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return isSymmetricChild(root.leftNode, root.rightNode);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree == null && rightTree == null) {
            return true;
        }

        if (leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
            return false;
        }

        if (leftTree.val != rightTree.val) {
            return false;
        }

        return isSymmetricChild(leftTree.leftNode, rightTree.rightNode) &&
                isSymmetricChild(leftTree.rightNode, rightTree.leftNode);
    }

    //给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    //对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
    //牛客236
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        if (p == root || q == root) {
            return root;
        }

        TreeNode leftNode = lowestCommonAncestor(root.leftNode, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.rightNode, p, q);

        if (leftNode != null && rightNode != null) {
            return root;
        }

        if (leftNode != null && rightNode == null) {
            return leftNode;
        }

        if (leftNode == null && rightNode != null) {
            return rightNode;
        }

        return null;
    }

    //给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
    //对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
    //牛客236
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        //将root到p和q的结点放到stack中
        findPath(root, p, stackP);
        findPath(root, q, stackQ);

        int lenP = stackP.size();
        int lenQ = stackQ.size();
        int len = Math.abs(lenP - lenQ);

        if (lenP > lenQ) {
            while (len != 0) {
                stackP.pop();
                len--;
            }
        } else if (lenP < lenQ) {
            while (len != 0) {
                stackQ.pop();
                len--;
            }
        }

        while (stackP.peek().val != stackQ.peek().val) {
            stackP.pop();
            stackQ.pop();
        }

        return stackP.peek();
    }
    private boolean findPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }

        stack.push(root);

        if (root.val == node.val) {
            return true;
        }

        boolean ret = findPath(root.leftNode, node, stack);
        if (ret == true) {
            return true;
        }

        ret = findPath(root.rightNode, node, stack);
        if (ret == true) {
            return true;
        }

        stack.pop();
        return false;
    }

    //给定两个整数数组 preorder 和 inorder
    //其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
    //力扣105
    public TreeNode buildTree(char[] preorder, char[] inorder) {
        return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
    }

    public int preIndex;
    public TreeNode buildTreeChild(char[] preorder, char[] inorder, int indexBegin, int indexEnd) {
        if (indexBegin > indexEnd) {
            return null;
        }
        int rootIndex = 0;
        for (int i = 0; i <= indexEnd; i++) {
            if (preorder[preIndex] == inorder[i]) {
                rootIndex = i;
                break;
            }
        }
        TreeNode newNode = new TreeNode(inorder[rootIndex]);
        preIndex++;

        newNode.leftNode = buildTreeChild(preorder, inorder, indexBegin, rootIndex - 1);
        newNode.rightNode = buildTreeChild(preorder, inorder, rootIndex + 1, indexEnd);

        return newNode;
    }

    //给定两个整数数组 inorder 和 postorder ，
    //其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
    //力扣106
    public static int curIndex;
    public static TreeNode buildTree2(char[] inorder, char[] postorder) {
        curIndex = postorder.length - 1;
        return buildTreeChild2(inorder, postorder, 0, postorder.length - 1);
    }

    public static TreeNode buildTreeChild2(char[] inorder, char[] postorder, int indexBegin, int indexEnd) {

        if (indexBegin > indexEnd) {
            return null;
        }
        int rootIndex = 0;

        for (int i = indexEnd; i >= indexBegin; i--) {
            if (postorder[curIndex] == inorder[i]) {
                rootIndex = i;
                break;
            }
        }

        curIndex--;

        TreeNode newNode = new TreeNode(inorder[rootIndex]);

        newNode.rightNode = buildTreeChild2(inorder, postorder, rootIndex + 1, indexEnd);
        newNode.leftNode = buildTreeChild2(inorder, postorder, indexBegin, rootIndex - 1);


        return newNode;
    }

    //给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
    //空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
    //力扣606
    public String tree2str(TreeNode root) {
        StringBuilder str = new StringBuilder();
        tree2strChild(root, str);
        return str.toString();
    }

    public void tree2strChild(TreeNode root, StringBuilder str) {
        if (root == null) {
            return;
        }
        str.append(root.val);
        if (root.leftNode != null) {
            str.append("(");
            tree2strChild(root.leftNode, str);
            str.append(")");
        } else {
            if (root.rightNode != null) {
                str.append("()");
            } else {
                return;
            }
        }

        if (root.rightNode != null) {
            str.append("(");
            tree2strChild(root.rightNode, str);
            str.append(")");
        } else {
            return;
        }
    }
}